题目链接
期望DP！
设 f[i] 表示到了第 i 位的总期望，g[i] 表示到了第 i 位结尾的连续 o 的期望长度，那么：
- 当 s[i] = x, 则 f[i] = f[i - 1], g[i] = 0.
- 当 s[i] = o, 则 f[i] = f[i - 1] + 2g[i - 1] + 1, g[i] = g[i - 1] + 1(这一步可以根据完全平方公式推出)
- 当 s[i] = ?, 则 f[i] = f[i - 1] + g[i - 1] + 0.5, g[i] = (g[i - 1] + 1) / 2.
我们发现转移时的状态只与上一轮的状态有关，所以可以使用滚动数组节省空间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include <bits/stdc++.h>
using namespace std;
int n, now;
char ch;
double f[2], g[2];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> ch;
if (ch == 'x') f[now ^ 1] = f[now], g[now ^ 1] = 0;
else if (ch == 'o') f[now ^ 1] = f[now] + 2 * g[now] + 1, g[now ^ 1] = g[now] + 1;
else f[now ^ 1] = f[now] + g[now] + 0.5, g[now ^ 1] = g[now] / 2 + 0.5;
now ^= 1;
}
printf("%.4lf\n", f[now]);
return 0;
}
|